In module 15 you will learn about three important tools in computer science and Python programming: data structures, algorithms, and big O notation.

15.2 Data structures

A data structure is way of representing data and a set of operations that are possible for that particular way of organizing data.

What data structures have you learned so far in this course? You may think of these Python data types when you hear the term “data structure”.

• integers
• floating point numbers
• strings
• lists
• tuples
• dictionaries
• sets

All these Python data types are relatively simple data structures. Each of these data types has a set of operations you can use to manipulate each one. And some operations you can do do on a str that you cannot do on a list. Even a simple float or int is considered to be a data structure. But usually you can understand these data types without taking a special course about data structures.

In module 15.2 you will learn about ways to combine all of the simple built-in Python data types to create ever more powerful data structures that can help you solve complex programming challenges, such as building a text adventure or chatbot.

15.3 Binary search algorithm and data structure

Have you ever needed to quickly search for something in a sorted sequence of things in the real world? What about searching for a hotel room in a big hotel with long hallways that go in a circle around the elevator? Or better yet, imagine you are driving at night in the rain in a big subdivision, and you need to get out of the car to shine a flashlight on the curb to check the street numbers painted on the curb, looking for a particular address. You are in a hurry and you don’t want to get wet, so you need to minimize the number of times you need to pull over and get out of your car. If you’re ever in this situation, the binary search algorithm will come in handy. You may have even already figured out this algoirthm for yourself, and after this lesson you will know its name and how to implement it in Python.

In module 15.3 you will learn about algorithms by implementing a search algorithm for finding values in a sorted list. An algorithm is a procedure, usually a function, designed to accomplish a general purpose task on a collection of data in a data structure. An algorithm is a list of rules, like a recipe, that you use to produce something useful out of data. You are already using an algoirthm each time you do long division to divide large numbers by hand. You even need an algorithm just to add large integers. You need to know how to “carry” the tens values whenever you add two digits that add up to more than nine.

And you can get ahead in life if you know some good algorithms for getting things done efficiently. For example if you’ve ever searched for an apartment in San Diego, you know how important it is to have an algorithm, if you need to find a place in a hurry. It turns out that, if you only have a month to find a place, the best approach is to reject all of the appartments that you see in the first 12 days. After that, you can safely sign a rental contract that is better (cheaper, bigger, or nicer) than all the others you checked out in the first 12 days. This is called the “40% rule” (12 days is 40% of a 30-day month) and is one of the many cool everyday algorithms in Algorithms to Live By that can help you get the most out of life or business.

The most common algorithm that you need to know about for job interviews at tech companies is the sort algorithm. For example, a sort algorithm is designed to take a list of objects and arrange them in ascending or descending order according to some rule. Sorting a list of strings in alphabetical order is a common example of a sort algorithm.

In module 15.3 you will learn about one particular algorithm call “binary search.”

you will learn in module 15.3 how to measure the speed of an

Another common algorithm is called “search.” You use a search algorithm when you have a large data structure and you want to find the location of a particular value hidden somewhere inside.

There are algorithms for searching almost all data structures. There are algorithms for searching an array of sorted numbers or strings or searching an unsorted array (list). You can even use search algorithms to speed up your search of complicated data structures such as a graph or tree. It turns out that AI decision making is a search algorithm, under the hood.

15.4 Time complexity

In module 15.4 and how to tell a good (fast) algorithm from a bad one and “time complexity” is how we measure that. What’s important about an algorithm is how long it takes to run as the number of objects grows. So if your sort algorithm takes 1 second to run on one object and 10 seconds to run on 10 objects, you can say that it has “linear time complexity.” You will learn how to analyze the pseudocode or Python code to estimate its time complexity, without having to test it on large numbers of objects. You can predict approximately how long it will take to run your algorithm on a million or a billion or even a trillion objects, without ever having to test it on all those objects. The “Big O Notation” is a way for you to write down this analysis and then compare one algorithm to another, giving your algorithm design a “grade” based on how fast it is. On the final exam you saw a list of “grades” for algorithms. Here is a cheat sheet of speed scores in Big O Notation, sorted from fastest to slowest.

• ”Constant”:O(1)
• ”Linear”: O(N)
• ”Logarithmic”: O(log(N))
• ”Linearithmic”: O(N*log(N))
• ”Quadratic”: O(N**2)
• ”Exponential”: 2**O(N)
• ”Factorial”: O(N!)

Wikipedia has a list of many more time complexity expressions in big O notation. Notice that all of these expressions have the capital letter “O” in them. This means “on the order of”, which means approximately or of proprotionate magnitude. And they also have the capital letter N as a variable inside the big O function.

It’s a powerful skill to be able to guess ahead of time, whether your algorithm design is going to be a good one or not. And it’s a great way to think about your Python program design as well.

In module 15.4 you will use the Big O Notation to analyze some sort and search algorithms, including your binary search algorithm from module 15.3.